home *** CD-ROM | disk | FTP | other *** search
/ Amiga Packmags / Source, The - Issue 5 (1993)(Epsilon)[WB].zip / Source, The - Issue 5 (1993)(Epsilon)[WB].adf / Source / Vectors / VectorSpace / PointInPoly.lha / pointnpolygon.txt1 < prev    next >
Internet Message Format  |  1989-10-24  |  3KB
  1. From albanycs!leah:rsb584 Mon Jan 18 13:56:21 1988
  2. Received: by albanycs.albany.edu (5.54/4.8)
  3.     id AA28580; Mon, 18 Jan 88 12:59:42 EST
  4. Date: Mon, 18 Jan 88 12:59:39 EST
  5. From: albanycs!leah:rsb584 ( Raymond S Brand)
  6. Received: by leah.Albany.EDU (5.58/1.1)
  7.     id AA16600; Mon, 18 Jan 88 12:59:39 EST
  8. Message-Id: <8801181759.AA16600@leah.Albany.EDU>
  9. To: albanycs:beowulf!rsbx
  10.  
  11. >From saponara@tcgould.tn.cornell.edu Wed Jan 13 09:19:53 1988
  12. Path: leah!uwmcsd1!bbn!rochester!cornell!batcomputer!saponara
  13. From: saponara@batcomputer.tn.cornell.edu (John Saponara)
  14. Newsgroups: comp.graphics
  15. Subject: Re: polygons and points
  16. Summary: A quick summary of yesterday's posting, for those in the know
  17. Keywords: computer graphics, polygons and points
  18. Message-ID: <3365@batcomputer.tn.cornell.edu>
  19. Date: 13 Jan 88 14:19:53 GMT
  20. References: <506UD138985@NDSUVM1> <22564@ucbvax.BERKELEY.EDU>
  21. Reply-To: saponara@tcgould.tn.cornell.edu (Eric Haines)
  22. Organization: 3D/Eye Inc, Ithaca, NY
  23. Lines: 41
  24.  
  25. In article <22564@ucbvax.BERKELEY.EDU> bsmith@postgres.berkeley.edu (Brian Smith) writes:
  26. >I had a hell-of-a-time finding it, but the algorithm for testing 
  27. >if a point is in a polygon can be found in
  28. >
  29. >Robert Sedgewick, "Algorithms", Addison-Wesley, 1984, pp 315-317.
  30. >
  31. >The basic idea is to draw a line from the point to infinity and
  32. >count how many intersections it makes with the polygon. If it 
  33. >crosses an odd number of times, then it's inside, otherwise it's
  34. >outside. Usually a horizontal line is chosen for efficiency, and
  35. >intersections of the line with vertices have to be handled
  36. >specially.
  37. >
  38. >    Brian Smith
  39.  
  40.     Thanks, I've been wanting a source to cite for this procedure.  Since
  41. people already in the know may not have plowed through my longwinded
  42. explanation of basically the same algorithm, which I posted yesterday, I
  43. thought I'd point out the nice addition to Sedgewick's explanation which makes
  44. all the "vertex on the testing ray" special cases go away.  We used the basic
  45. algorithm outlined by Sedgewick for years at Cornell and then at 3D/Eye.  About
  46. two years ago I found yet another bug in this darn routine, one of those "if
  47. the first vertex starts on the ray and a second vertex touches the ray when..."
  48. type obscure cases that come up once in a million polygons.  (Berlin talks
  49. about similar problems in "Efficiency Considerations in Image Synthesis"
  50. SIGGRAPH Course Notes, Vol. 11, 1985.  By the way, this article gives three
  51. methods for doing point/polygon comparisons.  Avoid his method, though - it is
  52. slower.  Sedgewick with the modification outlined below is the way to go).
  53. After some frustration with getting rid of all those special cases, I happened
  54. upon a simplification which is very useful. 
  55.  
  56.     Anyway, the modification is that the ray traced along the horizontal
  57. axis should not be considered a set of points at all, but rather is simply a
  58. dividing line between zero and the negative numbers along the Y axis.  This
  59. change leads to a wonderful simplification:  there are now no vertices which
  60. are intersected by the ray, i.e. no special cases!  Now all polygon vertices
  61. are either above or below this new sort of ray (which is really just a boundary
  62. instead of a true ray).  This change made for faster, simpler, and correct
  63. code.  Try it - it works!
  64.  
  65. Eric Haines, 3D/Eye Inc (borrowing John Saponara's account)
  66.  
  67.  
  68.